package com.problem.leetcode;

import com.google.common.base.Stopwatch;

/**
 * @author didi
 * @DESCRIPTION
 * @create 2019-05-10 14:41
 **/

public class Problem645 {

    public int[] findErrorNums(int[] nums) {
        for (int i = 0; i < nums.length; i++){
            while (nums[i] != i+1 && nums[nums[i]-1] != nums[i]){//i位置应该出现的数，将i位置实际出现的数换到应该出现的位置；
                swap(nums, i, nums[i]-1);
            }
        }
        for (int i = 0; i < nums.length; i++){
            if (nums[i] != i+1){
                return new int[]{nums[i], i+1};
            }
        }
        return null;

    }

    public void swap(int [] arr, int l, int r){
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }


    // public int[] findErrorNums(int[] nums) {
    //     int   sameValue = -1;
    //     int[] target    = new int[2];
    //     int   sum       = 0, sourceSum = 0, count = 1;
    //     for (int index = 0; index < nums.length; index++) {
    //         sum += count++;
    //         sourceSum += nums[index];
    //     }
    //
    //     for (int index = 0; index < nums.length; ) {
    //         if (index + 1 != nums[index] && nums[index] != nums[nums[index] - 1]) {
    //             int tmp = nums[nums[index] - 1];
    //             nums[nums[index] - 1] = nums[index];
    //             nums[index] = tmp;
    //         } else if (nums[index] != index + 1) {
    //             //发现了重复元素
    //             sameValue = nums[index];
    //             break;
    //         } else {
    //             ++index;
    //         }
    //     }
    //     target[0] = sameValue;
    //     target[1] = sum > sourceSum ? target[0] + sum - sourceSum : target[0] + sum - sourceSum;
    //
    //     return target;
    // }

    public static void main(String[] args) {
        Stopwatch  stopwatch  = Stopwatch.createStarted();
        Problem645 problem645 = new Problem645();
        for (int index = 0; index < 30000000; index++) {
            problem645.findErrorNums(new int[]{1, 2, 2, 4});
        }
        stopwatch.stop();
        System.out.println(stopwatch.toString());


    }

}
